Registermaschine

Regịstermaschine,

 

Automatentheorie: Modell eines Automaten, durch das der Begriff der Berechenbarkeit (berechenbare Funktion) definiert werden kann; es besitzt eine Reihe von Speicherplätzen (Registern), die während einer Berechnung leer sind oder Zeichenreihen eines vorgegebenen Alphabets enthalten. Die Rechnung einer Registermaschine erfolgt nach einem Registerprogramm, das aus Anweisungszeilen besteht (v. a. Verlängerungs-, Verkürzungs-, Sprunganweisungen sowie einer Druck- und Stoppanweisung). Eine Funktion f (x) heißt registerberechenbar, wenn es ein Registerprogramm gibt, sodass eine geeignete Registermaschine aus dem Argument x in endlich vielen Schritten den Funktionswert f (x) berechnet. Man kann zeigen, dass alle registerberechenbaren Funktionen auch allgemein-rekursiv sind und umgekehrt. Ein der Registermaschine ähnliches mathematisches Modell ist die Turing-Maschine.